class Solution:
    def sortString(self, s: str) -> str:
        mem = [0] * 26
        res = []
        length = len(s)
        for char in s:
            mem[ord(char) - ord("a")] += 1
        print(mem)
        # return
        while len(res) < length:
            for i in range(26):
                print(mem[i], mem)
                if mem[i]:
                    res.append(chr(i + ord("a")))
                    mem[i] -= 1

            for i in range(25, -1, -1):
                if mem[i]:
                    res.append(chr(i + ord("a")))
                    mem[i] -= 1
            print(res)
        return "".join(res)


if __name__ == "__main__":
    Solution().sortString("rat")
